1. Technical Field
The present invention relates to a cache memory for data storage in general and, in particular, to a cache memory having redundant cache lines. Still more particularly, the present invention relates to a mechanism for cache-line replacement within a cache memory having redundant cache lines.
2. Description of the Prior Art
During manufacturing process, all integrated circuits (ICs) are tested for manufacturing defects. Any IC that is found to be defective will be discarded. In order to improve the yield of the manufacturing process, it is well-known in the industry to include redundant circuits within an IC. For example, multiple redundant rows and columns are often included in memory devices for replacing rows and columns that may be inoperative due to manufacturing defects. Further, a fuse link is commonly connected between the input pin and the internal circuitry of the IC. If a defective location is identified and the defect can be corrected by substituting a redundant circuit for an inoperative circuit within the IC, then the fuse link is disconnected, for example, by laser zapping, to enable a functional redundant circuit over the defective circuit. The manufacturing process is then completed and the IC is packaged to be sold to customers.
For modern microprocessors, on-chip random access memories (RAMs) are commonly employed in cache memory implementations. Moreover, redundant cache lines are also provided within these on-chip cache memories, and the aforementioned technique is utilized to select a redundant cache line when an "original" cache line is found to be defective. As an example, a cache memory having 128 cache lines may be implemented with two redundant cache lines such that the cache memory has an array of 130 cache lines in total. During manufacturing tests, cache line faults within the cache memory are analyzed. If there is no cache line fault found in the cache memory, none of the redundant cache lines will be enabled. However, if there is a cache line fault found, the faulty cache line will be disabled by a set of fuses and one of the two redundant cache lines will be enabled. Thus, the cache memory will exit the manufacturing process with 128 cache lines enabled and two cache lines disabled.
In general, it is useful to have a cache-line replacement scheme that can efficiently utilize the physical design of the cache memory. More importantly, such cache-line replacement scheme should be able to select a cache line that is not currently allocated, and such cache-line replacement scheme should ignore the nonselected redundant lines in an efficient manner. Consequently, it would be desirable to provide a mechanism for cache-line replacement that allocates vacant locations or pseudo-random locations in a cache memory having redundant cache lines.